package com.xcc.dataStructures.demo06_algorithm;

/**
 * 基数排序
 */
public class RadixSort {

    public static void main(String[] args) {
        /*int[] arr = {32, 7, 123, 11, 90, 5, 1};
        radixSort(arr);*/
        int data = 80000000;//8000w数据 4110ms
        int[] arr = new int[data];
        for (int i = 0; i < data; i++) {
            arr[i] = (int) (Math.random() * data);
        }
//        int[] arr = {32, 7, 12, 11, 90, 5, 1};
        long startTime = System.currentTimeMillis();
        radixSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("时长：" + ((endTime - startTime))); //大概耗时2438ms
    }

    /**
     * 基数排序
     */
    public static void radixSort(int[] arr) {
        if (arr == null) {
            return;
        }
        int maxLength = getMaxLength(arr);
        //定义二维数组表示10个桶  每个桶中转入的数值最多为arr.length
        int[][] bucket = new int[10][arr.length];
        //定义一维数组 用于记录每个余数上一共有多少个数据
        int[] indexs = new int[10];
        //第一层循环每次需要基数为i
        for (int i = 0, u = 1; i < maxLength; i++, u *= 10) {
            //第二层循环在指定的bucket中存储数据
            for (int j = 0; j < arr.length; j++) {
                //获取当前数字的余数
                int mod = (arr[j] / u) % 10;
                //将每条数据填充到二维数组中
                bucket[mod][indexs[mod]] = arr[j];
                //同时对应的桶上的数量 +1
                indexs[mod] += 1;
            }

            int d = 0;
            //获取每个桶上的元素数量
            for (int k = 0; k < indexs.length; k++) {
                //如果当前桶上有数据
                if (indexs[k] != 0) {
                    for (int j = 0; j < indexs[k]; j++) {
                        //将当前桶上的绑定数据赋值给arr  进行一次arr的排序
                        arr[d] = bucket[k][j];
                        d++;
                    }
                }
                //将索引清空，防止索引越界
                indexs[k] = 0;
            }

//            System.out.println("第" + (i + 1) + "次数据为: " + Arrays.toString(arr));
        }


    }

    /**
     * 获取数组中最大值得长度
     */
    private static int getMaxLength(int[] arr) {
        if (arr == null) {
            return 0;
        }
        //首先求出最大数
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        //获取最大数的长度
        int maxLength = (max + "").length();
        return maxLength;
    }


}
